# 两数之和IV-输入BST
# 给定一个二叉搜索树root和一个目标结果k
# 如果BST中存在两个元素且它们的和等于给定的目标结果，则返回true

# Definition for a binary tree node.
# class HOT.TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque


class Solution:

    def __init__(self):
        self.set = set()

    # 深度优先搜索+set存值
    def findTarget(self, root, k: int) -> bool:
        if root is None:
            return False
        val = root.val
        if k - val in self.set:
            return True
        self.set.add(val)
        return self.findTarget(root.left, k) or self.findTarget(root.right, k)

 # # 广度有限搜索+set
 #   def findTarget(self, root, k: int) -> bool:
 #       s = set()
 #       q = deque([root])
 #       while q:
 #           node = q.pop()
 #           if k - node.val in s:
 #               return True
 #           if node.left:
 #               q.append(node.left)
 #           if node.right:
 #               q.append(node.right)
 #       return False
 #
 #   # 中序遍历+双指针
 #   def findTarget(self, root, k: int) -> bool:
 #       arr = []
 #       def inorderTraversal(node) -> None:
 #           if node:
 #               inorderTraversal(node.left)
 #               arr.append(node.val)
 #               inorderTraversal(node.right)
 #
 #       inorderTraversal(root)
 #
 #       left, right = 0, len(arr) - 1
 #       while left < right:
 #           sum = arr[left] + arr[right]
 #           if sum == k:
 #               return True
 #           if sum < k:
 #               left += 1
 #           else:
 #               right -= 1
 #       return False
